#include <iostream>
using namespace std;

#include <vector>

// 算法思路总结：
// 1. 非递归实现归并排序（迭代法）
// 2. 从最小间隔开始，逐步倍增进行两两归并
// 3. 处理边界情况：第二段不存在或第二段超出数组范围
// 4. 使用临时数组存储归并结果，避免频繁内存分配
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(n)

void MergeSortNonR(vector<int>& v)
{
    int gap = 1;
    int n = v.size();
    vector<int> tmp(n);

    while (gap < n)
    {
        for (int i = 0 ; i < n ; i += 2 * gap)
        {
            // [i, i + gap - 1], [i + gap, i + 2 * gap - 1]
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            if (begin2 >= n)
            {
                break;
            }

            if (end2 >= n)
            {
                end2 = n - 1;
            }
            
            int index = begin1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (v[begin1] < v[begin2])
                {
                    tmp[index++] = v[begin1++];
                }
                else
                {
                    tmp[index++] = v[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[index++] = v[begin1++];
            }

            while (begin2 <= end2)
            {
                tmp[index++] = v[begin2++];
            }

            for (int j = i ; j <= end2 ; j++)
            {
                v[j] = tmp[j];
            }
        }
        gap *= 2;
    }
}

int main()
{
    vector<int> v1 = {9,8,7,6,5,4,3,2,1};
    vector<int> v2 = {1,3,5,4,2};

    MergeSortNonR(v1);
    MergeSortNonR(v2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}